package com.wang.utils.sort;

import sun.applet.Main;

import java.util.Arrays;

/**
 * @author 86173
 * @date 2021/7/30 18:41
 */

/**
 * 归并排序时间复杂度   O(N)
 * 分治策略
 * 将数据拆成叫小的分支，进行操作
 */
public class MergeSort {

	public static void main(String[] args) throws Exception {
		int[] arr = {1,9,8,2,4};
		MergeSort me = new MergeSort();

		int[] sort = me.sort(arr);
		System.out.println(Arrays.toString(sort));
	}

	public int[] sort(int[] sourceArray) throws Exception {
		// 对 arr 进行拷贝，不改变参数内容
		int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

		//不断拆，直到arr.length < 2
		if (arr.length < 2) {
			return arr;
		}
		int middle = (int) Math.floor(arr.length / 2);

		int[] left = Arrays.copyOfRange(arr, 0, middle);
		int[] right = Arrays.copyOfRange(arr, middle, arr.length);

		return merge(sort(left), sort(right));  //递归处理数据
	}

	//将有序子序列合并
	//以前一个有序序列的每一个位置与后一序列依次比较，将需要的值插入合适位置
	//剩余的没有比较的值直接合道最后序列的后面
	protected int[] merge(int[] left, int[] right) {
		int[] result = new int[left.length + right.length];
		int i = 0;
		while (left.length > 0 && right.length > 0) {
			if (left[0] <= right[0]) {
				result[i++] = left[0];
				left = Arrays.copyOfRange(left, 1, left.length);
			} else {
				result[i++] = right[0];
				right = Arrays.copyOfRange(right, 1, right.length);
			}
		}

		while (left.length > 0) {
			result[i++] = left[0];
			left = Arrays.copyOfRange(left, 1, left.length);
		}

		while (right.length > 0) {
			result[i++] = right[0];
			right = Arrays.copyOfRange(right, 1, right.length);
		}

		return result;
	}
}
